The sequential importance sampling (SIS) algorithm has gained considerablepopularity for its empirical success. One of its noted applications is to thebinary contingency tables problem, an important problem in statistics, wherethe goal is to estimate the number of 0/1 matrices with prescribed row andcolumn sums. We give a family of examples in which the SIS procedure, if runfor any subexponential number of trials, will underestimate the number oftables by an exponential factor. This result holds for any of the usual designchoices in the SIS algorithm, namely the ordering of the columns and rows.These are apparently the first theoretical results on the efficiency of the SISalgorithm for binary contingency tables. Finally, we present experimentalevidence that the SIS algorithm is efficient for row and column sums that areregular. Our work is a first step in determining the class of inputs for whichSIS is effective.
展开▼
